package com.example.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/9
 * 路径总和二
 */
public class PathSumPlus {
    /**
     * 这道题主要考察递归加回溯，递归完之后就回溯
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum)
    {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> listList = new ArrayList<>();
        if(root==null){
            return listList;
        }
        dfs(root,list,listList,targetSum,0);
        return listList;
    }

    private void dfs(TreeNode root, List<Integer> list, List<List<Integer>> listList, int targetSum,int sum) {
        if(root==null){
            return;
        }
        sum=sum+root.val;
        if(root.left==null&&root.right==null&&sum==targetSum){
            list.add(root.val);
            listList.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        list.add(root.val);
        dfs(root.left,list,listList,targetSum,sum);
        dfs(root.right,list,listList,targetSum,sum);
        list.remove(list.size()-1);
    }
}
